<!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta name="robot" content="index,follow">
<title>Module acn - AVL binary tree cell node module - Forth Foundation Library</title>
</head>
<body>
<h2>acn - AVL binary tree cell node module</h2>
<h3>Module Description</h3>
<p>The acn module implements a node in an AVL binary tree. The acn structure
extends the bcn structure.
</p>
<h3>Module Words</h3>
<dl>
</dl>
<h4>AVL Tree node structure</h4>
<dl>
<dt><a name="word1"><b>acn%</b>	( -- n )</dt>
<dd>Get the required space for an acn node</dd>
</dl>
<h4>Node creation, initialisation and destruction</h4>
<dl>
<dt><a name="word2"><b>acn-init</b>	( x1 x2 acn1 acn2 -- )</dt>
<dd>Initialise the node acn2 with the parent acn1, key x2 and data x1</dd>
<dt><a name="word3"><b>acn-new</b>	( x1 x2 acn1 -- acn2 )</dt>
<dd>Create a new node acn2 on the heap with parent acn1, key x2 and data x1</dd>
<dt><a name="word4"><b>acn-free</b>	( acn -- )</dt>
<dd>Free the node from the heap</dd>
</dl>
<h4>Inspection</h4>
<dl>
<dt><a name="word5"><b>acn-dump</b>	( acn -- )</dt>
<dd>Dump the node</dd>
</dl>
<h3>Examples</h3>
<pre>
include ffl/act.fs
include ffl/bci.fs
include ffl/str.fs
include ffl/enm.fs


\ Example1: store mountain height in a AVL tree with numerical keys

\ The mountain enumeration

begin-enumeration
  enum: MountEverest
  enum: MontBlanc
  enum: MountElbrus
  enum: Vaalserberg
end-enumeration


\ Create the AVL tree on the heap and store it in the heights variable

act-new value heights


\ Add the mountain heights in the tree; the key is the mountain enum value

8300 MountEverest heights act-insert
4819 MontBlanc    heights act-insert
5642 MountElbrus  heights act-insert


\ Find a mountain height in the tree

MontBlanc heights act-get [IF]
  .( Mount:mont blanc height:) . cr
[ELSE]
  .( Mount:mont blanc not in tree.) cr
[THEN]

Vaalserberg heights act-get [IF]
  .( Mount:vaalserber height:) . cr
[ELSE]
  .( Mount:vaalserberg not in tree.) cr
[THEN]


\ Free the heights tree from the heap

heights act-free



\ Example2: store mountain height in a AVL tree with string keys


\ Create the AVL tree in the dictionary

act-create mountains


\ Setup the compare word for comparing the mountain names

: mount-compare  ( str str - n = Compare the two mountain names )
  str^ccompare
;

' mount-compare mountains act-compare!


\ Add the mountain heights to the AVL tree; the key is the mountain name in a (unique) dynamic string

8300 str-new dup s" mount everest" rot str-set  mountains act-insert
4819 str-new dup s" mont blanc"    rot str-set  mountains act-insert
5642 str-new dup s" mount elbrus"  rot str-set  mountains act-insert


\ Find a mountain height in the AVL tree

str-new value mount-name

s" mont blanc" mount-name str-set

mount-name mountains act-get [IF]
  .( Mount:)        mount-name str-get type 
  .(  height:)      . cr 
[ELSE]
  .( Mount:) mount-name str-get type .(  not in tree.) cr
[THEN]


s" vaalserberg" mount-name str-set

mount-name mountains act-get [IF]
  .( Mount:)        mount-name str-get type 
  .(  height:)      . cr 
[ELSE]
  .( Mount:) mount-name str-get type .(  not in tree.) cr
[THEN] 


\ Word for printing the mountain heights

: mount-emit ( x x -- = Print mountain )
  str-get type ."  --&gt; " . cr
;


\ Print all mountain heights

' mount-emit mountains act-execute       \ Execute the word mount-emit for all entries in the tree


\ Example binary tree iterator

\ Create the tree iterator in the dictionary (use bci also for AVL trees)

mountains bci-create mount-iter          \ Create an iterator named mount-iter on the mountains tree


\ Using the iterator

mount-iter bci-first [IF]
  .( First mount:) mount-iter bci-key drop str-get type 
  .(  height:)     . cr 
[ELSE]
  .( No first mountain.) cr
[THEN]

mount-iter bci-last [IF]
  .( Last mount:) mount-iter bci-key drop str-get type 
  .(  height:)    . cr
[ELSE]
  .( No last mountain.) cr
[THEN]


\ Cleanup the tree

mountains act-clear
</pre>
<hr>
<div align="center">generated 24-Jul-2010 by <b>ofcfrth-0.10.0</b></div>
</body>
</html>
